// 112 easy 路径总和

// 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
// 说明: 叶子节点是指没有子节点的节点。
//
// 示例:
// 给定如下二叉树，以及目标和 sum = 22，
//
//               5
//               / \
//             4   8
// /   / \
//           11  13  4
// /  \      \
//         7    2      1
// 返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
//


/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {boolean}
 */
var hasPathSum = function(root, sum) {
//    只能深搜 先序遍历
    if(!root) return false;
    let flag = false
    let fn = (cNode, sum) => {
        if (!cNode.left && !cNode.right){
            if (cNode.val === sum) {
                flag = true;
            }
        }
        if(cNode.left){
            fn(cNode.left, sum - cNode.val);
        }
        if(cNode.right){
            fn(cNode.right, sum - cNode.val);
        }
    }
    fn(root, sum)
    return flag;
};